package com.example.leetcode.DFS;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 题目描述
 * 给定一个大小为 n 的正方形国际象棋棋盘，求有多少种方式可以放置 n 个皇后并使得她们互
 * 不攻击，即每一行、列、左斜、右斜最多只有一个皇后。
 * 输入输出样例
 * 输入是一个整数 n，输出是一个二维字符串数组，表示所有的棋盘表示方法。
 * Input: 4
 * Output: [
 * [".Q..", // Solution 1
 * "...Q",
 * "Q...",
 * "..Q."],
 * ["..Q.", // Solution 2
 * "Q...",
 * "...Q",
 * ".Q.."]
 * ]
 * 在这个样例中，点代表空白位置，Q 代表皇后。
 *
 * @Description https://leetcode-cn.com/problems/n-queens/solution/jian-dan-hui-su-shuang-90-by-xdz0201-ib18/
 * @date 2021/5/24 13:39
 * @Author liuzhihui
 * @Version 1.0
 */
public class Solution_7_51 {
    public static void main(String[] args) {

    }
    List<List<String>> results = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        //初始化棋盘
        char[][] chessboard  = new char[n][n];

        //使用‘.’填充棋盘
        for (char[] line : chessboard) {
            Arrays.fill(line,'.');
        }
        //从第一行开始找n皇后
        backTrace(chessboard, n , 0);
        return results;
    }

    //回溯法
    private void backTrace(char[][] chessboard, int n, int row) {
        // 递归出口：找到了一种n皇后的解法
        if (row == chessboard.length){
            List<String> temp = new ArrayList<>();
            //将棋盘中的一种N皇后的解法，添加到结果集中
            for (char[] chars : chessboard) {
                temp.add(String.valueOf(chars));
            }
            results.add(temp);
            return;
        }

        //遍历当前行row的每一列数据
        for (int colunm = 0; colunm < n; colunm++) {
            //判断当前元素设置为Q，是否会合法
            if (!isValid(colunm, chessboard,n,row)){
                continue;
            }
            // 可以进行当前row的皇后的落子
            chessboard[row][colunm] = 'Q';
            // 下一行找可以落子的皇后
            backTrace(chessboard, n ,row + 1);
            // 回溯：找其他皇后的解法
            chessboard[row][colunm] = '.';
        }
    }
    //判断皇后落子是否合格：
    // 判断行(无需判断，因为如果当前这个点落子皇后合法，那么，就会到下一行去找另一个皇后，所以当前行就只有一个皇后，等每一行都找到了皇后，就是一组解法，回溯回来，就是去找其他新的解法了)、
    // 列、
    // 左上与右上
    private boolean isValid(int colunm, char[][] chessboard, int n, int row) {
        // 判断列,是否已经存在皇后了
        for (int i = 0; i < n; i++) {
            //已经存在皇后了，不合法
            if (chessboard[i][colunm] == 'Q'){
                return false;
            }
        }
        // 判断当前点的右上是否存在皇后,右上的点对应的是(竖边-n, 横边+n)
        for(int j = colunm + 1, i = row - 1; j < n && 0 <= i; j++, i--){
            //已经存在皇后了，不合法
            if (chessboard[i][j] == 'Q'){
                return false;
            }
        }
        // 判断当前点的左上是否存在皇后,左上的点对应的是(竖边-n,横边-n)
        for(int j = colunm - 1, i = row - 1; j >= 0 && 0 <= i; j--, i--){
            //已经存在皇后了，不合法
            if (chessboard[i][j] == 'Q'){
                return false;
            }
        }
        //到此说明皇后落子合格
        return true;
    }

    //pratice1----------------------------------------------------------------------------------------------------------
    public List<List<String>> solveNQueens1(int n){
        // 初始化棋盘
        char[][] chessboard = new char[n][n];
        // 使用'.'填充棋盘
        for (char[] chars : chessboard) {
            Arrays.fill(chars,'.');
        }
        // 从第一行开始找皇后
        backTrace1(chessboard,n,0);
        return results;
    }
    //回溯法
    private void backTrace1(char[][] chessboard, int n, int row) {
        // 递归出口：找到了一组皇后
        if (chessboard.length == row){
            List<String> temp = new ArrayList<>();
            for (char[] chars : chessboard) {
                temp.add(String.valueOf(chars));
            }
            results.add(temp);
            return;
        }
        // 遍历当前行的列
        for (int i = 0; i < n; i++) {
            if (!isValid1(chessboard,row,n,i)){
                continue;
            }
            // 可以落子
            chessboard[row][i] = 'Q';
            // 下一行落子
            backTrace1(chessboard,n,row + 1);
            // 回溯
            chessboard[row][i] = '.';
        }
    }
    // 判断是否可以进行皇后的落子
    private boolean isValid1(char[][] chessboard, int row, int n, int col) {
        //列
        for (int i1 = 0; i1 < n; i1++) {
            if (chessboard[i1][col]=='Q'){
                return false;
            }
        }
        // 右上(竖边-n, 横边+n)
        for(int i = col + 1, j = row -1; i < n && j >= 0; j--, i++ ){
            if (chessboard[j][i]=='Q'){
                return false;
            }
        }

        // 左上(竖边-n, 横边-n)
        for(int i = col - 1, j = row -1; i >= 0 && j >= 0; j--, i--){
            if (chessboard[j][i]=='Q'){
                return false;
            }
        }
        return true;
    }
    //pratice2----------------------------------------------------------------------------------------------------------
    /**
     * 思路：
     * 1、填充棋盘‘。’ ， 从第一行开始找皇后
     * 2、递归出口。
     * 3、基于当前行，遍历列，寻找当前行的皇后
     *      基于列寻找，右上寻找，左上寻找
     * 4、寻找到了，就到下一行寻找，找到了一组解，就回溯，继续寻找下一个答案
     */
    public List<List<String>> solveNQueens2(int n){
        //初始化棋盘并填充棋盘
        char[][] chessboard = new char[n][n];
        for (char[] chars : chessboard) {
            Arrays.fill(chars, '.');
        }
        // 从第一行开始找皇后
        backTrace2(chessboard, n ,0);
        return results;
    }
    private void backTrace2(char[][] chessboard, int n, int row) {
        // 递归出口
        if (chessboard.length == row){
            List<String> temp = new ArrayList<>();
            for (char[] chars : chessboard) {
                temp.add(String.valueOf(chars));
            }
            results.add(temp);
            return;
        }
        // 遍历列
        for (int col = 0; col < n; col++) {
            // 判断当前元素是否可以落子
            if (!isValid2(chessboard,n,row,col)){
                continue;
            }
            // 可以落子
            chessboard[row][col] = 'Q';
            // 下一行找落子
            backTrace2(chessboard, n, row + 1);
            // 回溯
            chessboard[row][col] = '.';
        }
    }
    private boolean isValid2(char[][] chessboard, int n, int row, int col) {
        for (int i = 0; i < n; i++) {
            if (chessboard[i][col] == 'Q'){
                return false;
            }
        }
        for (int i = row - 1, j =  col + 1; i >= 0 &&  j < n; i--,j++ ){
            if (chessboard[i][j] == 'Q'){
                return false;
            }
        }
        for (int i = row - 1, j =  col - 1; i >= 0 &&  j >= 0; i--,j--){
            if (chessboard[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }
}
